#pragma once
#include <iostream>
#include <vector>

using namespace std;

template <class Type>
struct BinTreeNode {
    Type data;
    BinTreeNode<Type>* left, * right;
};

template <class Type>
class binTree {
protected:
    BinTreeNode<Type>* root;

    template <class T>
    friend void DeepCopySubTree(BinTreeNode<T>* p, const BinTreeNode<T>* exist);
    void InOrderSubTree(const BinTreeNode<Type>* p, void (*Visit)(const Type&)) const;
    void PreOrderSubTree(const BinTreeNode<Type>* p, void (*Visit)(const Type&)) const;
    void PostOrderSubTree(const BinTreeNode<Type>* p, void (*Visit)(const Type&)) const;
    virtual void ClearSubTree(BinTreeNode<Type>** p);
public:
    enum Status { SUCCESS, NO_SPACE };

    binTree() { root = NULL; }
    binTree(const Type& e);
    binTree(const binTree<Type>& other) { DeepCopySubTree(root, other.root); }
    binTree<Type>& operator=(const binTree<Type>& other) { Clear(); DeepCopySubTree(root, other.root); }

    bool IsEmpty() const { return root == NULL; }

    void GetElem(const BinTreeNode<Type>* p, Type& e) const { e = p.data; }
    void SetElem(const BinTreeNode<Type>* p, const Type& e) { p.data = e; }
    void SetRoot(const Type& e) { root = new BinTreeNode<Type>; root->data = e; root->left = NULL; root->right = NULL; }

    void InOrder(void (*Visit)(const Type&)) const { InOrderSubTree(root, Visit); }
    void PreOrder(void (*Visit)(const Type&)) const { PreOrderSubTree(root, Visit); }
    void PostOrder(void (*Visit)(const Type&)) const { PostOrderSubTree(root, Visit); }

    Status InsertLeftChild(BinTreeNode<Type>* p, const Type& e);
    Status InsertRightChild(BinTreeNode<Type>* p, const Type& e);

    virtual void Clear() { ClearSubTree(&root); root = NULL; };

    virtual ~binTree() { Clear(); }
};

template <class T>
void DeepCopySubTree(BinTreeNode<T>* p, const BinTreeNode<T>* exist) {
    if (exist) {
        p = new BinTreeNode<T>;
        p->data = exist->data;
        p->left = NULL;
        p->right = NULL;
        DeepCopyTree(p->left, exist->left);
        DeepCopyTree(p->right, exist->right);
    }
}

template <class Type>
void binTree<Type>::InOrderSubTree(const BinTreeNode<Type>* p, void (*Visit)(const Type&)) const {
    if (p) {
        InOrderSubTree(p->left, Visit);
        (*Visit)(p->data);
        InOrderSubTree(p->right, Visit);
    }
}

template <class Type>
void binTree<Type>::PreOrderSubTree(const BinTreeNode<Type>* p, void (*Visit)(const Type&)) const {
    if (p) {
        (*Visit)(p->data);
        PreOrderSubTree(p->left, Visit);
        PreOrderSubTree(p->right, Visit);
    }
}

template <class Type>
void binTree<Type>::PostOrderSubTree(const BinTreeNode<Type>* p, void (*Visit)(const Type&)) const {
    if (p) {
        PostOrderSubTree(p->left, Visit);
        PostOrderSubTree(p->right, Visit);
        (*Visit)(p->data);
    }
}

template <class Type>
binTree<Type>::binTree(const Type& e) {
    root = new BinTreeNode<Type>;
    if (root) {
        root->data = e;
        root->left = NULL;
        root->right = NULL;
    }
}

template <class Type>
typename binTree<Type>::Status binTree<Type>::InsertLeftChild(BinTreeNode<Type>* p, const Type& e) {
    if (p->left)
        ClearSubTree(&(p->left));
    p->left = new BinTreeNode<Type>;
    p->left->data = e;
    p->left->left = NULL;
    p->left->right = NULL;
    // DEBUG
    //printf("Insert left child:%c 0x%pH from 0x%pH\n", p->left->data, p->left, p);

    return SUCCESS;
}

template <class Type>
typename binTree<Type>::Status binTree<Type>::InsertRightChild(BinTreeNode<Type>* p, const Type& e) {
    if (p->right)
        ClearSubTree(&(p->right));
    p->right = new BinTreeNode<Type>;
    p->right->data = e;
    p->right->left = NULL;
    p->right->right = NULL;
    // DEBUG
    //printf("Insert left child:%c 0x%pH from 0x%pH\n", p->right->data, p->right, p);

    return SUCCESS;
}

template <class Type>
void binTree<Type>::ClearSubTree(BinTreeNode<Type>** p) {
    if ((*p) == NULL)
        return;
    if ((*p)->left == NULL && (*p)->right == NULL) {
        delete (*p);
        (*p) = NULL;
    }
    else {
        ClearSubTree(&((*p)->left));
        ClearSubTree(&((*p)->right));
    }
}

template <class Type>
class BST : public binTree<Type>
{
public:
    void InsertChild(const Type& num);
};

template <class Type>
void BST<Type>::InsertChild(const Type& num) {
    BinTreeNode<Type>* p = binTree<Type>::root;
    while (p != NULL) {
        if (p->data == num)
            return;
        if (num < p->data) {
            if (p->left != NULL)
                p = p->left;
            else {
                p->left = new BinTreeNode<Type>;
                p->left->data = num;
                p->left->left = NULL;
                p->left->right = NULL;
                return;
            }
        }
        else {
            if (p->right != NULL)
                p = p->right;
            else {
                p->right = new BinTreeNode<Type>;
                p->right->data = num;
                p->right->left = NULL;
                p->right->right = NULL;
            }
        }
    }
}
